package Test;

/**
 * @author Kevin
 * @date 2020/3/1 11:57
 */
public class HeapSort2 {

    public static int findKthLargest(int[] arr, int k) {
        buildHeap(arr, k);

        for (int i = k; i < arr.length; i ++) {
            if (arr[i] < arr[0]) continue;
            swap(arr, i, 0);
            heapify(arr, k, 0);//代替堆中最小值，进行堆化
        }
        return arr[0];
    }

    public static void buildHeap(int[] arr, int k) {
        for (int i = (k-1)/2; i >=0; i--) {
            heapify(arr, k, i);
        }
    }

    public static void heapify(int[] arr, int k, int i) {
        int maxPos = i;
        while (true) {
            if (i * 2 + 1 < k && arr[i*2+1] > arr[i]) maxPos = i*2+1;
            if (i * 2 + 2 < k && arr[i*2+2] > arr[maxPos]) maxPos = i*2+2;
            if (maxPos == i) break;
            swap(arr, i, maxPos);
            i = maxPos;
        }
    }

    public static void swap(int[] a, int i, int j) {
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
}
